from typing import *

from math import inf


class Solution:

    def maxScore(self, nums: List[int], x: int) -> int:

        n = len(nums)
        if n == 1:
            return nums[0]
        f = [[-inf] * 2 for _ in range(n)]
        f[0][0] = nums[0] if nums[0] & 1 == 0 else -inf
        f[0][1] = nums[0] if nums[0] & 1 == 1 else -inf
        for i in range(1, n):
            if nums[i] & 1 == 0:
                if f[i - 1][0] != -inf:
                    f[i][0] = f[i - 1][0] + nums[i]
                if f[i - 1][1] != -inf:
                    f[i][0] = max(f[i][0], f[i - 1][1] + nums[i] - x)
                f[i][1] = f[i - 1][1]
            else:
                if f[i - 1][0] != -inf:
                    f[i][1] = f[i - 1][0] + nums[i] - x
                if f[i - 1][1] != -inf:
                    f[i][1] = max(f[i][1], f[i - 1][1] + nums[i])
                f[i][0] = f[i - 1][0]

        return max(f[n - 1])


class Solution:

    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        a = nums[0] if nums[0] & 1 == 0 else -inf
        b = nums[0] if nums[0] & 1 == 1 else -inf
        for i in range(1, n):
            ai, bi = -inf, -inf
            if nums[i] & 1 == 0:
                if a != -inf:
                    ai = a + nums[i]
                if b != -inf:
                    ai = max(ai, b + nums[i] - x)
                bi = b
            else:
                if a != -inf:
                    bi = a + nums[i] - x
                if b != -inf:
                    bi = max(bi, b + nums[i])
                ai = a
            a, b = ai, bi
        return max(a, b)


class Solution:

    def maxScore(self, nums: List[int], x: int) -> int:
        o = e = -inf
        if nums[0] & 1 == 0:
            e = nums[0]
        else:
            o = nums[0]
        for i in range(1, len(nums)):
            num = nums[i]
            if num & 1 == 0:
                e = max(e, o - x) + num
            else:
                o = max(o, e - x) + num
        return max(o, e)


s = Solution()
print(s.maxScore(nums=[2, 3, 6, 1, 9, 2], x=5))
print(s.maxScore(nums=[2, 4, 6, 8], x=3))
